package com.javaDemo.ti;

import java.util.*;

/**
 * 回溯算法经典问题详解
 * 
 * @author csy
 * @description 面试中常见的回溯算法题目的详细解析
 */
public class BacktrackingExamples {

    /**
     * 【组合问题】组合总和
     * 
     * 问题描述：
     * 给定一个无重复元素的正整数数组candidates和一个正整数target，
     * 找出candidates中所有可以使数字和为target的组合。
     * candidates中的数字可以无限制重复被选取。
     * 
     * 解题思路详解：
     * 1. 为什么用回溯？
     * - 需要找到所有可能的组合
     * - 每个数字可以重复使用，形成决策树
     * 
     * 2. 回溯三要素：
     * a) 选择列表：candidates数组中的所有数字
     * b) 路径：当前已经选择的数字
     * c) 结束条件：
     * - 当前和等于target（收集结果）
     * - 当前和超过target（剪枝）
     * 
     * 3. 优化策略：
     * - 排序数组以便提前剪枝
     * - 使用start参数避免重复组合
     * 
     * 4. 举例详解：
     * 输入：candidates = [2,3,6,7], target = 7
     * 决策树分析：
     * []
     * / / \ \
     * 2 3 6 7
     * / | \ | \ |
     * 2 3 6 3 6 6
     * /|\ |
     * 2 3 6 3
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 存储所有符合条件的组合结果
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0)
            return results;

        // 排序数组，为后续的剪枝优化做准备
        Arrays.sort(candidates);
        backtrackCombination(candidates, target, 0, new ArrayList<>(), 0, results);
        return results;
    }

    private void backtrackCombination(int[] candidates, int target, int sum,
            List<Integer> current, int start, List<List<Integer>> results) {
        // 找到一个符合条件的组合，将其添加到结果集
        if (sum == target) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            // 剪枝优化：如果当前数字加上已有和超过目标值，由于数组已排序，后面的数字更大，因此可以直接结束循环
            if (sum + candidates[i] > target)
                break;

            // 选择当前数字，将其加入路径
            current.add(candidates[i]);
            // 递归调用，注意传入i而不是i+1，因为每个数字可以重复使用
            backtrackCombination(candidates, target, sum + candidates[i], current, i, results);
            // 回溯：撤销选择，将当前数字从路径中移除
            current.remove(current.size() - 1);
        }
    }

    /**
     * 【排列问题】全排列
     * 
     * 问题描述：
     * 给定一个不含重复数字的数组nums，返回其所有可能的全排列。
     * 
     * 解题思路详解：
     * 1. 为什么用回溯？
     * - 需要穷举所有可能的排列顺序
     * - 每个位置都需要尝试所有未使用的数字
     * 
     * 2. 回溯三要素：
     * a) 选择列表：所有未被使用的数字
     * b) 路径：当前已经选择的数字序列
     * c) 结束条件：路径长度等于数组长度
     * 
     * 3. 关键点：
     * - 使用visited数组标记已使用的数字
     * - 需要考虑每个位置放置每个数字的可能性
     * 
     * 4. 举例详解：
     * 输入：nums = [1,2,3]
     * 决策树分析：
     * []
     * / | \
     * 1 2 3
     * / \ / \ / \
     * 2 3 1 3 1 2
     * | | | | | |
     * 3 2 3 1 2 1
     */
    public List<List<Integer>> permute(int[] nums) {
        // 存储所有可能的排列结果
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return results;

        // 使用visited数组标记已经使用过的数字
        boolean[] visited = new boolean[nums.length];
        backtrackPermute(nums, visited, new ArrayList<>(), results);
        return results;
    }

    private void backtrackPermute(int[] nums, boolean[] visited,
            List<Integer> current, List<List<Integer>> results) {
        // 当前排列已经完成（长度等于数组长度），将其添加到结果集
        if (current.size() == nums.length) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 跳过已经使用过的数字
            if (visited[i])
                continue;

            // 标记当前数字为已使用
            visited[i] = true;
            // 将当前数字加入排列
            current.add(nums[i]);
            // 递归生成下一个位置的排列
            backtrackPermute(nums, visited, current, results);
            // 回溯：撤销选择
            current.remove(current.size() - 1);
            // 取消标记，表示当前数字可以再次使用
            visited[i] = false;
        }
    }

    /**
     * 【子集问题】子集
     * 
     * 问题描述：
     * 给定一个整数数组nums，返回该数组所有可能的子集（幂集）。
     * 解集不能包含重复的子集。
     * 
     * 解题思路详解：
     * 1. 为什么用回溯？
     * - 需要生成所有可能的组合
     * - 每个元素都有选择和不选择两种状态
     * 
     * 2. 回溯三要素：
     * a) 选择列表：当前位置之后的所有数字
     * b) 路径：当前已选择的数字集合
     * c) 结束条件：到达数组末尾
     * 
     * 3. 实现策略：
     * - 每个位置都有两种选择：选或不选
     * - 使用start参数控制选择范围
     * 
     * 4. 举例详解：
     * 输入：nums = [1,2,3]
     * 决策树分析：
     * []
     * / \
     * [1] []
     * / \ / \
     * [1,2] [1] [2] []
     * / \ / \ / \ / \
     * [1,2,3][1,2][1,3][1][2,3][2] [3] []
     */
    public List<List<Integer>> subsets(int[] nums) {
        // 存储所有可能的子集
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null)
            return results;

        // 从空集开始，通过回溯生成所有子集
        backtrackSubsets(nums, 0, new ArrayList<>(), results);
        return results;
    }

    private void backtrackSubsets(int[] nums, int start,
            List<Integer> current, List<List<Integer>> results) {
        // 每个路径都是一个有效的子集，直接添加到结果集
        results.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            // 选择当前数字
            current.add(nums[i]);
            // 递归生成包含当前数字的子集，注意从i+1开始，避免重复
            backtrackSubsets(nums, i + 1, current, results);
            // 回溯：撤销选择
            current.remove(current.size() - 1);
        }
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        BacktrackingExamples solution = new BacktrackingExamples();

        // 测试组合总和
        System.out.println("=== 组合总和测试 ===");
        int[] candidates = { 2, 3, 6, 7 };
        int target = 7;
        System.out.println("输入数组：" + Arrays.toString(candidates));
        System.out.println("目标和：" + target);
        System.out.println("所有组合：" + solution.combinationSum(candidates, target) + "\n");

        // 测试全排列
        System.out.println("=== 全排列测试 ===");
        int[] nums1 = { 1, 2, 3 };
        System.out.println("输入数组：" + Arrays.toString(nums1));
        System.out.println("所有排列：" + solution.permute(nums1) + "\n");

        // 测试子集
        System.out.println("=== 子集测试 ===");
        int[] nums2 = { 1, 2, 3 };
        System.out.println("输入数组：" + Arrays.toString(nums2));
        System.out.println("所有子集：" + solution.subsets(nums2));
    }
}